The field of computer graphics concerns the creation, storage, manipulation and display of pictures and models of objects by a digital processor. Color encoders are widely used in computer graphics and color television display systems for encoding the color signals to be displayed on the display screen. FIG. 1 illustrates a simplified prior art computer graphics display system in which the respective green, red and blue digitized color information data generated by a computer system (not shown) are input to respective encoders 10R, 10G and 10B, where they are separately encoded, for storage in a frame buffer 12. The values stored in the frame buffer 12, referred to herein as "pixel values", correspond to ones of the original color information data originally generated by the computer system and input to the encoders 10R, 10G and 10B. The pixel values stored in the frame buffer are used as indices into color lookup tables or color maps 14R, 14G and 14B for determining the actual color to illuminate each pixel in a display device 18. Sometimes, gamma (.gamma.) correction is built into the color maps 14R, 14G, 14B to correct for non-linearities in the display device. The resulting data read from the color maps 14R, 14G and 14B is converted to analog voltages by respective digital to analog converters (DACs) 16R, 16G, 16B, and these analog voltages are applied to the display device 18 in accordance with well-known techniques. Optionally, the DACs could be replaced with drivers for a liquid crystal display (LCD).
Note that the reference to 8 bits in FIG. 1 is exemplary only; while 8 bit color data is typical, such is not required.
One of the problems with prior art computer graphics systems of the type illustrated in FIG. 1 is that the encoders 10R, 10G and 10B are designed to reduce the bit length of the color information data generated by the computer system (e.g., the 8 bit RGB color components shown in FIG. 1) prior to storage in the frame buffer 12. This is done to minimize the size of the required frame buffer 12, thereby minimizing memory requirements and reducing the cost of the system. In many prior art systems, the encoding is performed by dithering the color information data for each color component (the RGB color components in the case of FIG. 1) then, in some dithering methods, truncating. Dithering results in lost color data at each pixel. Though the background and detailed description portions of this application may sometimes describe dithering as including an optional truncating step, the invention is not so limited, and the invetion encompasses any dithering method, irrespective of whether or not truncating is employed.
Dithering is well known in the art. See, for example, Fundamentals of Interactive Computer Graphics, J. D. Foley and A. Van Dam, ISBN: 0-201-14468-9. See also, for example, U.S. Pat. No. 4,956,638. Both of these are incorporated herein by reference. In general, dithering is a technique wherein noise is injected into a signal, and then the signal is quantized. More specifically, in computer graphics, dithering means adding a noise signal to the full precision color components at each pixel. The new signal is then quantized to some predetermined number of levels. For example, if the full precision of a color component is represented as an 8 bit number (i.e., the color can take on a value from 0 to 255), then, at each pixel, a small amount of noise (typically less than or equal to 5 bits) is combined with the color component. This new value is then quantized to some smaller number of bits, typically 3. One commonly used quantization method is truncation. The result of this process is illustrated in FIGS. 19A-C (described hereinafter) and in detail in respect to FIG. 2 (described hereinafter). However, it should be noted that there are many different noise function and quantization methods that may be used. One such method is disclosed in the aforementioned U.S. Pat. No. 4,956,638. It should also be noted that one important property of dithering is that, since the color is sampled at each pixel, the values stored at each pixel in the frame buffer will provide a reasonable approximation of the full precision color that it represents. A disadvantage of dither is that the viewing of dithered images is visually annoying because of the artifacts introduced by the dithering process.
Thus, the function of dithering is to permit use of a reduced number of available intensity levels to simulate a larger range of intensity levels. The prior art example of FIG. 1 illustrates a typical case where the computer system generates an 8-bit color information word for each color component, and the encoders 10R, 10G dither and optionally truncate to provide 3-bit pixel values for the R and G color components, and the encoder 10B dithers and truncates to provide a 2-bit pixel value for the B color component. This type of encoding, known as 3-3-2 encoding, is well known in the art. By way of another example, the computer system may generate the same 8-bit RGB color components, and the encoders 10R, 10G and 10B might each provide corresponding 4-bit pixel values. This type of encoding, known as 4-4-4 encoding, is also well known in the art.
Either way, the encoding results in a reduced number of colors available for display. In the example of FIG. 1, where each color component has 8-bits prior to encoding, there are (2.sup.8).sup.3, or 16,777,216 colors available for display prior to encoding. After encoding, each of the R and G color components has only 3 bits, and the B component has only 2 bits and only (2.sup.3).sup.2 .times.2.sup.2, or 256 colors, are available for display. In a 4-4-4 encoding system, where each color component is the same 8 bits long before encoding, only (2.sup.4).sup.3, or 4096, colors are available after encoding. This reduction in available intensities by the use of dither gives rise to visible artifacts in the display.
It should also be noted that the components need not necessarily be RGB, but may be YUV instead, where Y is the luminance component, U is blue-yellow difference component, and V is the red-yellow difference component. Though the prior art and the invention are described herein as using RGB components, it should be understood that this is for purposes of explanation only, and that the invention is not limited thereto. The invention encompasses use of the YUV components, or even other components, as well.
FIG. 2 illustrates application of the dithering technique explained in connection with FIG. 1, and how this encoding technique may give rise to artifacts. In particular, FIGS. 2A-2D illustrate application of the dithering technique to one of the color components, it being understood from above that this technique is applied by each of the encoders 10R, 10G, and 10B to each of the color components.
FIG. 2A illustrates a hypothetical frame for one color component of a hypothetical image having relatively flat color fields (i.e., no color changes) on the left and right sides of an edge E. An edge is defined as a color transition, e.g., a change in magnitude of one or more of the RGB components. Each block in FIG. 2A contains a color information value, in decimal, for a corresponding pixel. As shown, the decimal value corresponding to each pixel on the left side of the edge E is 4.5 and the decimal value corresponding to each pixel on the right side of the edge E is 6.75. In binary terms (where only two binary digits are needed to the right of a "binary point" to represent the quarter decimal values of 1/4, 1/2 and 3/4), these values translate to 100.10 and 110.11, respectively, as shown in FIG. 2A.
A hypothetical dither matrix for this color component is illustrated in FIG. 2B. The dither matrix of FIG. 2B has four dither cells, each with the quarter decimal values shown therein. Those skilled in the art will readily appreciate that application of the dither matrix of FIG. 2B to the decimal color component values of the image of FIG. 2A will, after quantization, result in 3-3-2 format data (where the binary digits to the right of the binary point are the values that are truncated), result in the binary values illustrated in FIG. 2C. FIG. 2D is the same as FIG. 2C except that the values are represented in decimal. In the prior art, it is the values of FIG. 2C that are stored in the frame buffer 12 as the pixel values. (However, note that if FIG. 2C were for the B component, there would be only 2 bits of data for each pixel when 3-3-2 encoding is used. Thus there would be only 2 bits of the B component stored in the frame buffer 12 for each pixel).
Thus, it will be appreciated, that FIG. 2A represents one color component of a hypothetical image as input to one of the decoders, e.g., 10R, 10G. FIG. 2D represents the output of that decoder. A comparison of FIG. 2D to FIG. 2A illustrates how and why artifacts occur in the image to be displayed. Whereas the color fields are perfectly flat to the left and right of the edge E in FIG. 2A, the same is not true after dithering and quantization, as shown in FIG. 2D. More importantly, it will be seen that the pixel values in FIG. 2D vary widely from their original corresponding values in FIGS. 2A. One result of this is that dither artifacts will be seen in the otherwise flat color region. Another result is that, whereas the edge E represented by the values of FIG. 2A would be "clean" if those values were used to display the image, the pixel values of FIG. 2D will cause the displayed edge E to appear jagged, or otherwise have artifacts.
In the prior art, some efforts have been made to increase the number of colors that can be displayed using the reduced number of storage elements in the frame buffer. These approaches rely primarily on color compression and decompression. For example, the Analog Devices family of ADV7148/ADV7141/ADV7146 integrated circuits, which embody a method known as Edsun Continuous Edge Graphics (CEG), employ a coloring encoding algorithm wherein color information and alpha values for each pixel are stored in an 8 bit deep frame buffer. These are mixed after the color map, then sent to the DAC. The result is that a single image may contain a different color at each pixel (i.e., over 1,000,000 different colors may be displayed in a single image). However, the Edsun CEG encoding algorithm is very complex, and, in order to update a new pixel, it is often necessary to read and decode many of the pixels that preceded it in the image in order to correctly-encode the new pixel. For these reasons, the Edsun CEG method is not well suited for high speed interactive graphics. Additionally, the Edsun CEG method is not well suited for windowed environments, e.g., Microsoft WINDOWS, since part of the color encoding information for a single pixel may be stored across several pixels, thus making some windowing operations very difficult. In other words, the color compression algorithms employ complex encoding algorithms that do not store a color sample for each pixel at that pixel's location in the frame buffer. It is this lack of a color sample at each pixel location that makes many graphics operations very difficult, thus limiting the interactive response of systems that use encoded frame buffers.
It is desirable to provide a color recovery method and apparatus that is capable of recovering most, if not all, of the color information that is lost during encoding. It is further desirable that the method and apparatus be fast and suited for high speed interactive systems, and that it be useful in windowed environments, yet be simple and inexpensive to implement. The present invention achieves all of these goals.